home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / dsp / dspgroup / fft32010.arc / README.LIS < prev   
Encoding:
File List  |  1986-01-18  |  8.4 KB  |  219 lines
  1. REFERENCE:
  2.  
  3. FFT32010 is a collect of 9 FFT programs written in the TMS32010 source code.
  4. These programs and the following writeup can be found in the Chapter 5 of
  5. "DFT/FFT and Convolution Algorithms - Theory and Implementation," C.S. Burrus
  6. and T.W. Parks, Wiley, 1985.
  7.  
  8.  
  9.  
  10.  
  11.           TABLE 5-1. TMS32010 ASSEMBLY LANGUAGE PROGRAM INDEX
  12.  
  13.  
  14.      _____________________________________________________________________
  15.      | PROGRAM            DESCRIPTION                PAGE |
  16.      |-------------------------------------------------------------------|
  17.      |      1    Direct DFT with table lookup                 148 |
  18.      |      2    Second-order Goertzel with forward-order input         152 |
  19.      |      3    Basic one-butterfly Cooley-Tukey radix-2 FFT         156 |
  20.      |      4    Basic one-butterfly radix-4 FFT              161 |
  21.      |      5    Three-butterfly radix-4 FFT with reduced storage     168 |
  22.      |      6    Straight-line 64-point radix-4 FFT             179 |
  23.      |      7    Two-butterfly radix-8 FFT                 190 |
  24.      |      8    Prime-factor algorithm FFT with unscrambling         205 |
  25.      |      9    Direct convolution routine                 220 |
  26.      ---------------------------------------------------------------------
  27.  
  28.  
  29.  
  30.  
  31.       Chapter 5.    TMS32010 ASSEMBLY LANGUAGE PROGRAMS
  32.                 FOR THE DFT AND CONVOLUTION
  33.  
  34.  
  35.       5.1    INTRODUCTION
  36.  
  37.       The TMS32010 assembly language programs in this chapter  are
  38.       based  on  the  FORTRAN routines from Chapter 4.  As much as
  39.       possible, these programs retain the  program    structure  and
  40.       variable  names  of their FORTRAN counterparts.  Many of the
  41.       comments in these programs are lines    of  FORTRAN  from  the
  42.       prototype routine which help explain the assembly language.
  43.  
  44.       The FORTRAN programs have been followed as much as  possible
  45.       to  retain  clarity and consistency.    At the same time, some
  46.       assumptions have been made to take advantage of the features
  47.       of  the  TMS32010  instruction  set.     First,  many  of  the
  48.       programs assume a minimal amount of external memory used  to
  49.       hold     the  data  which  is  addressed  via  peripheral  I/O
  50.       instructions, i.e., an address is initially sent to  a  data
  51.       address  counter and then the data word read from or written
  52.       to the memory.  A  counter  is  used    to  address  the  data
  53.       locations  sequentially  since  complex  data  is used whose
  54.       structure consists of the real  and  imaginary  parts  of  a
  55.       number  in  consecutive  memory locations.  A Q15 format for
  56.       number  representation  is  assumed    for   all   data   and
  57.       coefficient    values.   This    format    (one  sign  bit  +  15
  58.       fractional bits;  the  absolute  value  of  all  represented
  59.       numbers   is    less  than  one)  simplifies  calculations  in
  60.       fixed-point machines, such as the  TMS32010  digital    signal
  61.       processor.    No  scaling  on  intermediate  values  in  the
  62.       calculation was done, thus helping to clarify the code.  For
  63.       most data input sequences, scaling is unnecessary since they
  64.       will not produce  accumulator  overflow  in  the  processor.
  65.       Table   lookup   of  coefficients  is  used  for  speed  and
  66.       simplicity.  These programs use a full size table (often the
  67.       size    of  the transform).  Smaller tables may be used at the
  68.       expense of speed if program memory  size  is    limited.   All
  69.       programs  have  been    assembled  using  a  Texas Instruments
  70.       cross-assembler  running  on    a  VAX    11-780    with  the  VMS
  71.       operating system.
  72.  
  73.  
  74.  
  75.       5.2 TMS32010 PROGRAMS
  76.  
  77.       Program 1 is a direct  DFT  similar  to  the    first  FORTRAN
  78.       program.   All  data    is  initially in on-chip data RAM, and
  79.       results are output sequentially.  The data is on page 0  and
  80.       is  addressed  indirectly with the auxiliary registers.  All
  81.       other variables are located on page 1 of the TMS32010.  Full
  82.       32-bit   intermediate   values   are    retained  for  maximum
  83.       accuracy.  Note that the 32-bit running sum  is  initialized
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.                                 Page 2
  105.  
  106.  
  107.       by  shifting    the first data point 15 bits which simulates a
  108.       multiply by one in Q15 format.  In this and  all  the  other
  109.       assembly  language  programs, arrays and loop counters start
  110.       at zero, unlike the FORTRAN routines.
  111.  
  112.       Program 2 is a TMS32010  implementation  of  a  second-order
  113.       Goertzel's  algorithm  with  forward-order inputs similar to
  114.       FORTRAN Program  4.  Like the DFT  program,  input  data  is
  115.       initially on page 0 of data RAM and is addressed indirectly.
  116.       Results are output sequentially.  The 2*cosine factor in the
  117.       inner  loop  is implemented by adding twice the product of a
  118.       single cosine multiply.  This 2*cosine term along  with  the
  119.       feedback  loop  make    this  algorithm  very  susceptible  to
  120.       quantization error and overflows on a  fixed-point  machine.
  121.       Since  no scaling is done in this algorithm, the data should
  122.       be scaled previously to guard against overflow.
  123.  
  124.       A single butterfly  radix-2  Cooley-Tukey  FFT,  similar  to
  125.       FORTRAN  Program  6,    is shown in Program 3.    All data is in
  126.       external  data  memory  using  hardware  described  in   the
  127.       introduction     of   this  chapter.   Because    the  real  and
  128.       imaginary parts of the complex input data are in  sequential
  129.       locations,  not  in  separate arrays, the data index I has a
  130.       value twice that in the corresponding FORTRAN routine.   The
  131.       variable  IE,  the  index increment for the coefficients, is
  132.       computed with multiplies by 2 (implemented with a shift)  in
  133.       order  to  eliminate    divisions  which are inefficient.  The
  134.       size of the transform is limited to a power of  2,  and  the
  135.       largest  transform  is  simply  a  function of the amount of
  136.       available program memory.  Program 4 is just like Program  3
  137.       but  with a single radix-4 butterfly.  The transform size is
  138.       limited to a power of 4.
  139.  
  140.       Program 5 is a radix-4  algorithm  with  three  butterflies,
  141.       similar to FORTRAN Program 13.  Both auxiliary registers are
  142.       used as loop counters in the program.  Auxiliary Register  1
  143.       (AR1) replaces K in the DO 10 loop, and Auxiliary Register 0
  144.       (AR0) is used in the DO 1 and DO 20 loops.  These  registers
  145.       are efficient as counters in code with a lot of loops.
  146.  
  147.       Program 6 is a 64-point complex  FFT    optimized  for    speed.
  148.       The    algorithm   is    a  three-butterfly  radix-4  with  all
  149.       straight-line code.  This program uses the macro  capability
  150.       of  the assembler to generate the code, which is almost 2800
  151.       lines long when expanded.  Three macros are  used,  one  for
  152.       each    type of butterfly.  All data begins and ends on page 0
  153.       of data RAM, and page 1  contains  two  temporary  locations
  154.       which  are  addressed  by  auxiliary    registers.  The 13-bit
  155.       immediate  coefficients  are    used  as  part    of  the   MPYK
  156.       (multilpy  immediate) instruction.  Butterflies are accessed
  157.       in the same order as in Program 5, and all data  points  are
  158.       addressed directly for speed.
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.                                 Page 3
  177.  
  178.  
  179.       A  radix-8  FFT  is  shown  in  Program  7.     This    is   a
  180.       two-butterfly  FFT and corresponds to Program 16 in FORTRAN.
  181.       Because this a radix-8  program,  there  are    half  as  many
  182.       external  data  accesses  as    for  the looped radix-4.  This
  183.       helps to speed up the program.  The tradeoff is  in  a  more
  184.       complex  program  and  fewer    transform  sizes  which can be
  185.       computed.
  186.  
  187.       Program 8 is a prime-factor FFT,  corresponding  to  FORTRAN
  188.       Program  17.     This program is specific for a length-63 PFA,
  189.       but the structure can be used for all module    and  transform
  190.       sizes.   Coefficients are in a table initially and then read
  191.       into    data  RAM  for    use  during  execution.   Because  the
  192.       unscrambling     is  not  an  in-place    algorithm,  the  final
  193.       unscrambled results are written to port 2, which corresponds
  194.       to arrays A and B in the FORTRAN program.
  195.  
  196.       A direct calculation    of  linear  convolution  is  shown  in
  197.       Program  9.    In this example, an infinite input sequence is
  198.       convolved with a 32-bit permanent sequence which  represents
  199.       the  impulse    response  of a bandpass filter.  Input is read
  200.       sequentially from port 0, and output is written to  port  1.
  201.       The  main  computation  in the convolution is done using the
  202.       pair of instructions, LTD  and  MPY,    which  multiplies  the
  203.       sequences  point  by point and shifts the input sequence for
  204.       the next loop.
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211.                    REFERENCE
  212.  
  213.       1. Texas Instruments, TMS32010 USER'S GUIDE. Houston, TX:
  214.          Texas Instruments, 1983.
  215.  
  216.  
  217.  
  218.  
  219.